package 分类.一维动规;


public class 相等子集 {


    public boolean canPartition(int[] nums) {
        int sum=0;
        for (int i:nums){
            sum+=i;
        }
        if(sum%2!=0){
            return false;
        }
        int[] dp=new int[sum/2+1];

        for (int i=0;i<= sum/2;i++){
            for (int j=sum/2;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[i-nums[i]]+nums[i]);
            }
        }
        return dp[sum/2]==sum/2;
    }
}
